package _17_剑指Offer;

import java.util.Arrays;

public class _51_剑指Offer数组中的逆序对 {

    public static void main(String[] args) {


        _51_剑指Offer数组中的逆序对 v = new _51_剑指Offer数组中的逆序对();
        int[] nums = {7, 5, 6, 4};
        System.out.println(v.reversePairs(nums));
        System.out.println(Arrays.toString(nums));

    }

    // 归并排序，计算逆序对的个数
    public int reversePairs(int[] nums) {
        return split(nums, 0, nums.length);
    }

    // 归并分割
    private int split(int[] nums, int begin, int end) {
        if (end - begin <= 1) return 0;

        int mid = (begin + end) >> 1;

        int total = 0;

        total += split(nums, begin, mid);
        total += split(nums, mid, end);

        total += merge(nums, begin, mid, end);
        return total;
    }

    // 合并数据
    private int merge(int[] nums, int begin, int mid, int end) {
        int[] newAry = new int[mid - begin];
        System.arraycopy(nums, begin, newAry, 0, newAry.length);
        int left = 0;
        int right = mid;
        int storeIndex = begin;
        int count = 0;
        while (left < newAry.length) {
            if (right < end && nums[right] < newAry[left]) {
                nums[storeIndex++] = nums[right++];
            } else {
                // 计算逆序对
                count += right - mid;
                nums[storeIndex++] = newAry[left++];
            }
        }
        return count;
    }


}
